package bintree.heap.leetcode;

//347. 前 K 个高频元素

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class Num347_TopKFreQueue {
    private class Freq implements Comparable<Freq>{
        private int key;
        private int times;

        private Freq(int key, int times) {
            this.key = key;
            this.times = times;
        }

        @Override
        public int compareTo(Freq o) {
            return this.times - o.times;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];

        Map<Integer,Integer> map =new HashMap<>();
        for(int i : nums){
            if(map.containsKey(i)){
                map.put(i,map.get(i) + 1);
            }else {
                map.put(i,1);
            }
        }

        Queue<Freq> queue = new PriorityQueue<>();
        for(Map.Entry<Integer,Integer> entry : map.entrySet() ){
            if(queue.size() < k){
                queue.offer(new Freq(entry.getKey(), entry.getValue()));
            }else {
                Freq freq = queue.peek();
                if(freq.times > entry.getValue()){
                    continue;
                }else {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));
                }
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().key;
        }
        return ret;
    }
}
